package com.shm.leetcode;

import java.util.Arrays;

/**
 * 628. 三个数的最大乘积
 * 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 *
 * 示例 1:
 *
 * 输入: [1,2,3]
 * 输出: 6
 * 示例 2:
 *
 * 输入: [1,2,3,4]
 * 输出: 24
 * 注意:
 *
 * 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
 * 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
 * @author SHM
 */
public class MaximumProduct {
    /**
     * 方法一：排序
     * 首先将数组排序。
     *
     * 如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
     *
     * 如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
     *
     * 综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N\log N)O(NlogN)，其中 NN 为数组长度。排序需要 O(N\log N)O(NlogN) 的时间。
     *
     * 空间复杂度：O(\log N)O(logN)，主要为排序的空间开销。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/
     * @param nums
     * @return
     */
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n =nums.length;

        return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
    }


    /**
     * 方法二：线性扫描
     * 在方法一中，我们实际上只要求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 为数组长度。我们仅需遍历数组一次。
     *
     * 空间复杂度：O(1)O(1)。
     * @param nums
     * @return
     */
    public int maximumProduct_2(int[] nums) {
        int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if(num<min1){
                min2 = min1;
                min1 = num;
            }else if(num<min2){
                min2 = num;
            }

            if(num>max1){
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num>max2){
                max3 = max2;
                max2 = num;
            }else if(num>max3){
                max3 = num;
            }


        }
        return Math.max(min1*min2*max1,max1*max2*max3);
    }
}
